﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    public class Solution15
    {
        public int[] SearchRange(int[] nums, int target)
        {
            int[] result = new int[2] { -1, -1 };
            int left = 0;
            int right = nums.Length - 1;
            if (nums.Length == 1)
            {
                return result;
            }
            if (nums.Length == 2)
            {
                if (nums[0] == target && nums[1] == target)
                {
                    result[0] = 0;
                    result[1] = 1;
                    return result;
                }
                else
                {
                    return result;
                }
            }
            List<int> list = new List<int>();          
            for (int i = 0; i < nums.Length - 1; i++)
            {
                if (nums[i]==target)
                {
                    list.Add(nums[i]);
                }            
            }
            if (list.Count >= 2)
            {
                while (left <= right)
                {
                    int mid = (left + right) / 2;
                    if (nums[mid] == target)
                    {
                        while (mid >= left && nums[mid] == target)
                        {
                            if(mid<=0)
                            {
                                result[0] = 0;                               
                            }
                            mid--;
                        }
                        if (mid>0)
                        {
                            result[0] = mid + 1;
                        }
                        mid = (left + right) / 2;
                        while (nums[mid] == target && mid <= right)
                        {
                            if (mid>=nums.Length-1)
                            {
                                result[1] = nums.Length - 1;
                                break;
                            }                          
                            mid++;
                        }
                        if (mid<nums.Length-1)
                        {
                            result[1] = mid - 1;
                        }                       
                        break;
                    }
                    else if (nums[mid] > target)
                    {
                        right = mid - 1;
                    }
                    else
                    {
                        left = mid + 1;
                    }
                }
                return result;
            }
            return result;
        }
    }
}
